package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0131.java
 * @Author : WangRuoyu
 * @Date 2023/11/1 21:55
 */


public class Q0131 {
    String str;
    List<String> tmp = new ArrayList<>();
    List<List<String>> res = new ArrayList<>();

    private boolean check(int l, int r) {
        for (; l < r; l++, r--) {
            if (str.charAt(l) != str.charAt(r)) return false;
        }
        return true;
    }

    private void dfs(int k) {
        if (k >= str.length()) {
            res.add(new ArrayList<>(tmp));
        }
        for (int i = k; i < str.length(); i++) {
            if (check(k, i)) {
                tmp.add(str.substring(k, i + 1));
                dfs(i + 1);
                tmp.remove(tmp.size() - 1);
            }
        }
    }

    public List<List<String>> partition(String s) {
        str = s;
        dfs(0);
        return res;
    }

    public static void main(String[] args) {
        Q0131 sl = new Q0131();
        String s = "aba";
        System.out.println(sl.partition(s));
    }
}